package g

/*
 * @lc app=leetcode.cn id=94 lang=golang
 *

 * [94] 二叉树的中序遍历
 树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
*/

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
	return recursionInorder(root)
}

//          1
//         / \
//        2   3
//       / \
//      4   5
//     /     \
//    6       8
//     \       \
//      7       9
// return []int{6, 7, 4, 2, 5, 8, 9, 1, 3}
func morrisInorder(root *TreeNode) []int {
	var ret []int
	for root != nil {
		if root.Left == nil { //没有左孩子，取值，访问右孩子
			ret = append(ret, root.Val)
			root = root.Right //右节点不一定是右孩子，可能是某个父节点
		} else {
			pre := root.Left //pre 节点就是当前 root 节点向左走一步，然后一直向右走到最后一个孩子节点(切记是孩子节点)
			//切记 pre.Right != root 用来保证只是访问孩子节点，因为pre.Right 可能指向 root 本身(下边借助pre.Right指向下个节点，可能是root)
			for pre.Right != nil && pre.Right != root {
				pre = pre.Right
			}
			if pre.Right == nil { //第一次访问pre必为空
				pre.Right = root //右子树指向它遍历的下个节点，利用叶子节点的右孩子记录下个访问点
				root = root.Left //访问左子树
			} else { //第二次访问pre必不为空，且pre.Right != nil表明p的左子树已经遍历完成
				ret = append(ret, root.Val) //访问含有左子树的父节点
				pre.Right = nil             //还原访问过的右节点指针，没有这句，leetcode会陷入死循环，why？
				root = root.Right           //左子树和父节点访问完成，开始访问右子树,right可能指向某个父节点
			}
		}
	}
	return ret
}

func recursionInorder(root *TreeNode) []int {
	var ret []int
	if root == nil {
		return ret
	}
	if root.Left != nil {
		ret = append(ret, recursionInorder(root.Left)...)
	}
	ret = append(ret, root.Val)
	if root.Right != nil {
		ret = append(ret, recursionInorder(root.Right)...)
	}
	return ret
}

// @lc code=end
